package collection

type Pos bool

const (
	LEFT  Pos = true
	RIGHT Pos = false
)

type _bstNode[T any] struct {
	val    T
	left   *_bstNode[T]
	right  *_bstNode[T]
	parent *_bstNode[T]
}
type BST[T any] struct {
	head    *_bstNode[T]
	len     int
	compare *func(a, b T) int
}

func CreateBST[T any](compare func(a, b T) int) *BST[T] {
	var b = new(BST[T])
	b.head = new(_bstNode[T])
	b.compare = &compare
	return b
}
func _BSTInsert[T any](parent, node *_bstNode[T], v T, flag Pos, compare *func(a, b T) int) {
	if node == nil {
		t := new(_bstNode[T])
		t.val = v
		t.parent = parent
		if flag {
			parent.left = t
		} else {
			parent.right = t
		}
		return
	}
	if (*compare)(node.val, v) == 1 {
		_BSTInsert(node, node.left, v, LEFT, compare)
	} else {
		_BSTInsert(node, node.right, v, RIGHT, compare)
	}
}
func (b *BST[T]) Add(vs ...T) {
	for _, v := range vs {
		_BSTInsert(b.head, b.head.left, v, LEFT, b.compare)
	}
}

func (b *BST[T]) Search(v T) (T, bool) {
	for now := b.head.left; now != nil; {
		switch (*b.compare)(now.val, v) {
		case 1:
			now = now.left
			break
		case -1:
			now = now.right
		case 0:
			return now.val, true
		}
	}
	return *new(T), false
}

func (b *BST[T]) Delete(v T) {
	var node *_bstNode[T]
	pos := LEFT
	for now := b.head.left; now != nil; {
		switch (*b.compare)(now.val, v) {
		case 1:
			now = now.left
			pos = LEFT
			break
		case -1:
			now = now.right
			pos = RIGHT
			break
		case 0:
			node = now
			break
		}
		if node != nil {
			break
		}
	}
	_removeBSTNode(node, pos)

}

func _removeBSTNode[T any](node *_bstNode[T], pos Pos) {
	if node.left != nil {
		now := node.left
		for now.right != nil {
			now = now.right
		}
		node.val = now.val
		_removeBSTNode(now, LEFT)
		return
	}
	if node.right != nil {
		now := node.right
		for now.left != nil {
			now = now.left
		}
		node.val = now.val
		_removeBSTNode(now, RIGHT)
		return
	}
	if pos == LEFT {
		node.parent.left = nil
	} else {
		node.parent.right = nil
	}

}
